//
// Created by user on 2022/3/15.
//

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
    };

ListNode* reverseList(ListNode* head) {
    if(!head || !head->next){
        return head;
    }
    ListNode *p = reverseList(head->next);

    head->next->next = head;
    head->next = nullptr;

    return p;
}

ListNode* rotateRight(ListNode* head, int k) {
    if(!head || !head->next)return head;
    int len = 0;
    ListNode *curr = head;
    while (curr){
        len++;
        curr=curr->next;
    }
    if(k%len==0)return head;
    k = k%len;

    //整体反转
    ListNode *newHead = reverseList(head);
    ListNode *ktNode = newHead;
    for (int i = 0; i < k-1; ++i) {
        ktNode = ktNode->next;
    }
    //反转前K个
    ListNode *nexNode = ktNode->next;
    ktNode->next = nullptr;

    //前k在反转
    ListNode *reHead = reverseList(newHead);
    //k个后面的反转,在拼接
    newHead->next = reverseList(nexNode);

    return reHead;

}